package leetcode.N801_N900;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/12/8 10:18 上午
 */
public class N842 {

    public static void main(String[] args) {
        N842 n = new N842();
        System.out.println(n.splitIntoFibonacci("1101111"));
    }

    public List<Integer> splitIntoFibonacci(String S) {
        int length = S.length();
        if (length < 3) {
            return new ArrayList<>();
        }
        // Integer最大值为十位数
        // 如果需要把s分割成三个数 则 第一个数位数n ≤ (length - 1) / 2
        int firstLength = Math.min(10, (length - 1) / 2);
        for (int i = 1; i <= firstLength; i++) {
            String firstString = S.substring(0, i);
            long firstLong = Long.parseLong(firstString);

            if (firstLong == 0) {
                // 如果第一个数是0 则直接进入第二层
                // Integer最大值为十位数
                // 如果需要把s分割成三个数 且第一个数长度为i 则第二个数长度 n ≤ (length - i) / 2
                int secondLength = Math.min(10, (length - i) / 2);
                for (int j = 1; j <= secondLength; j++) {
                    String secondString = S.substring(i, i + j);
                    long secondLong = Long.parseLong(secondString);
                    // 虽然是10位数 但是也有可能超过integer的最大值
                    if (secondLong > (long) Integer.MAX_VALUE) {
                        continue;
                    }
                    List<Integer> result = new ArrayList<>();
                    result.add((int)firstLong);
                    result.add((int)secondLong);
                    if (check(firstLong, secondLong, i + j, S, result)) {
                        return result;
                    }
                }
                // 如果第二层无解  则无解
                return new ArrayList<>();
            }
            // 虽然是10位数 但是也有可能超过integer的最大值
            if (firstLong > (long) Integer.MAX_VALUE) {
                continue;
            }
            // Integer最大值为十位数
            // 如果需要把s分割成三个数 且第一个数长度为i 则第二个数长度 n ≤ (length - i) / 2
            int secondLength = Math.min(10, (length - i) / 2);
            for (int j = 1; j <= secondLength; j++) {
                String secondString = S.substring(i, i + j);
                long secondLong = Long.parseLong(secondString);
                if (secondLong == 0) {
                    // 如果第二个数是0开头 则直接check
                    List<Integer> result = new ArrayList<>();
                    result.add((int)firstLong);
                    result.add(0);
                    if (check(firstLong, 0, i + 1, S, result)) {
                        return result;
                    } else {
                        // 跳出第二层循环
                        break;
                    }
                }
                // 虽然是10位数 但是也有可能超过integer的最大值
                if (secondLong > (long) Integer.MAX_VALUE) {
                    continue;
                }
                List<Integer> result = new ArrayList<>();
                result.add((int)firstLong);
                result.add((int)secondLong);
                if (check(firstLong, secondLong, i + j, S, result)) {
                    return result;
                }
            }
        }
        return new ArrayList<>();
    }

    private boolean check(long firstLong, long secondLong, int index, String s, List<Integer> result) {
        if (index >= s.length()) {
            return false;
        }
        long sum = firstLong + secondLong;
        if (sum > (long) Integer.MAX_VALUE) {
            return false;
        } else {
            int length = String.valueOf(sum).length();
            String newString = s.substring(index, Math.min(index + length, s.length()));
            if (String.valueOf(sum).equals(newString)) {
                result.add((int)sum);
                if (index + length == s.length()) {
                    return true;
                }
                return check(secondLong, sum, index + length, s, result);
            } else {
                return false;
            }
        }
    }
}
